
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Random;

public class IDAStarSolutionFinder implements SolutionFinder 
{

	private volatile boolean finished = false;
	private volatile String solution = "";
//	private volatile HashMap<Integer,VisitedEntry> visitedMap = new HashMap<Integer,VisitedEntry>();
//	private volatile ConcurrentHashMap<Integer,VisitedEntry> visitedMap = new ConcurrentHashMap<Integer,VisitedEntry>();
	
//	private HashMap<Integer,VisitedEntry> visitedMap;
	
	private volatile Object finishedLock = new Object();

//	MoveRule naiveMoveRule;
	
//	HashSet<Integer> visitedSet = new HashSet<Integer>();
	
	Random random = new Random();
	
	
	private static int iterationCounter = 0;
	
	private static MoveRule playeMoveRule = new PlayerMove();
	
//	static DistanceCache distanceCache;
	
//	private static MoveRule boxMoveRule = new BoxMove();
	
//	private static final int DEPTH_PER_ITERATION = Integer.MAX_VALUE-10;
//	private static final int DEPTH_PER_ITERATION = 12;
	
	@Override
	public String FindSolution( Board.CellType[][] cellBoard ) 
	{
		
		Board board = new BoardImplFast( cellBoard );
		board.init(cellBoard);
		BoardImplFastReverse reverseBoard = new BoardImplFastReverse( cellBoard );
		reverseBoard.init(cellBoard);
		
		List<Board> reverseStartBoards = reverseBoard.spawnStartBoards();
		
		
		
		if ( Client.PRINT_COMMENTS_OLLE )
		{
			board.printBoard();
			reverseBoard.printBoard();
			
			System.out.println("boxes = "+board.getBoxes().length);
			System.out.println("reverseStartBoards.size() = " + reverseStartBoards.size() );
		}
		

		
		DistanceCache distanceCacheForward = new DistanceCacheMegaMatrix( (Board) board );
		DistanceCache distanceCacheBackwards = new DistanceCacheMegaMatrix( (Board) reverseBoard );
//		distanceCache = new ManhattanDistanceCache( (Board) board );
		
		long before = System.currentTimeMillis();
		
//		boolean[][] deadlocks = AndraDeadlockArray.create( board );
//		boolean[][] deadlocks = CreateDeadLockArray.create( board );
//		
//		AndraDeadlockArray.printBoolocks( deadlocks );
		
		
		
		MoveRule naiveMoveRuleForward = new NaiveMoveWithDeadlocks( ((Board)board).getDeadlockArray() );
//		naiveMoveRule = new NaiveMove();
		MoveRule naiveMoveRuleReverse = new NaiveMoveReverse();

//		Board originalBoard = board.clone();
		
//		for ( int depth = DEPTH_PER_ITERATION; 
//				depth < Integer.MAX_VALUE;
//				depth = depth + DEPTH_PER_ITERATION )
//		{
//			AStarSearch( board.clone(), depth);
//			AStarSearch( board.clone() );
			
//			System.out.println("IDA-depth = "+depth);
			
//			if ( finished )
//			{
//				break;
//			}
//		}
//		AStarSearch( board );
		
		
//		visitedMap = new HashMap<Integer,VisitedEntry>();
		
		ArrayList<Board> forwardBoards = new ArrayList<Board>(1);
		forwardBoards.add( board.clone() );
		
//		SearchThread threadForward = new SearchThread( (Board) board.clone() );
		SearchThread threadForward = new SearchThread( forwardBoards, BoardPath.BeginDirection.Forward, naiveMoveRuleForward, distanceCacheForward );
		SearchThread threadBackwards = new SearchThread( reverseStartBoards, BoardPath.BeginDirection.Backwards, naiveMoveRuleReverse, distanceCacheBackwards );
//		long startTime = System.currentTimeMillis();
		new TimeoutThread().start();
		threadForward.start();
		threadBackwards.start();
		
//		if ( Client.USE_TIMEOUTS )
//		{
//			while ( !finished )
//			{
//				try {
//					Thread.sleep(1000);
//				} catch (InterruptedException e) {
//					// TODO Auto-generated catch block
//					e.printStackTrace();
//				}
//				
//				if ( (System.currentTimeMillis()-startTime) > Client.TIMEOUT )
//				{
//					solution = "null";
//					finished = true;
//					break;
//				}
//			}
//		}
//		else
//		{
			synchronized( finishedLock )
			{
				if ( !finished )
				{
					try 
					{
						finishedLock.wait();
					} 
					catch (InterruptedException e) 
					{
						// TODO Auto-generated catch block
						e.printStackTrace();
					}
				}
			}
//		}
		

//		System.out.println("solution ="+solution);
		
//		SolutionConfirmer.confirm(board, solution);
		
		if ( Client.PRINT_COMMENTS_OLLE )
		{
			System.out.println( "Time = " + (System.currentTimeMillis()-before) );
			System.out.println("iterationCounter = "+iterationCounter);
		}


		
		
		return solution;
	}
	
	private class TimeoutThread extends Thread
	{
		public void run()
		{
			long startTime = System.currentTimeMillis();
			
			while ( !finished )
			{
				
				long timeLeft = (Client.TIMEOUT+startTime) - System.currentTimeMillis();
				
				synchronized( finishedLock )
				{
					
//					if ( (System.currentTimeMillis()-startTime) > Client.TIMEOUT )
					if ( timeLeft < 0 )
					{
						solution = "null";
						finished = true;
						finishedLock.notifyAll();
						break;
					}		

				}
				
				try {
//					Thread.sleep( Client.TIMEOUT );
					Thread.sleep( timeLeft );
				} catch (InterruptedException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
				
			}
		}
	}
	
	private class SearchThread extends Thread
	{
		
		List<Board> boards;
		BoardPath.BeginDirection direction;
		MoveRule moveRule;
		DistanceCache distanceCache;
		
		public SearchThread( List<Board> boards, BoardPath.BeginDirection direction, MoveRule moveRule, DistanceCache distanceCache )
		{
			this.boards = boards;
			this.direction = direction;
			this.moveRule = moveRule;
			this.distanceCache = distanceCache;
		}
		
		@Override
		public void run()
		{
			AStarSearch( boards, direction, moveRule, distanceCache );
		}
	}
	
	private void reportSolution( String solution )
	{
		synchronized( finishedLock )
		{
			if ( !finished )
			{
				finished = true;
				
				finishedLock.notifyAll();
			}
			else
			{
				return;
			}

		}
	}
	
//	public void AStarSearch( Board oldBoard, int maxDepth )
	public void AStarSearch( List<Board> oldBoards, BoardPath.BeginDirection direction, MoveRule moveRule, DistanceCache distanceCache )
	{
		
		HashMap<Integer,VisitedEntry> visitedMap = new HashMap<Integer,VisitedEntry>();
		PriorityQueue<BoardPath> queue = new PriorityQueue<BoardPath>();
		
		
		for ( Board oldBoard : oldBoards )
		{
			VisitedEntry entry = new VisitedEntry( oldBoard.hashCode(), null, null, direction );
			visitedMap.put( oldBoard.hashCode() , entry);
//			queue.add( new BoardPath( oldBoard, "", 0, BoardPath.BeginDirection.Forward, boxManhattanDistanceMatrix, null, distanceCache ) );
			queue.add( new BoardPath( oldBoard, "", 0, direction, null, distanceCache ) );
		}
		
//		VisitedEntry entry = new VisitedEntry( oldBoard.hashCode(), null, null );
//		visitedMap.put( oldBoard.hashCode() , entry);
////		queue.add( new BoardPath( oldBoard, "", 0, BoardPath.BeginDirection.Forward, boxManhattanDistanceMatrix, null, distanceCache ) );
//		queue.add( new BoardPath( oldBoard, "", 0, BoardPath.BeginDirection.Forward, null, distanceCache ) );
		
		if ( Client.PRINT_COMMENTS_OLLE )
		{
			System.out.println("Start states = " + queue.size() );
		}
		
		
		while ( !queue.isEmpty() )
		{

			BoardPath boardPath = queue.remove();
						
//			System.out.println("currentState = \t"+boardPath.board.hashCode());
			
			AStarSearch( boardPath, visitedMap, queue, moveRule, distanceCache );
						
		}
		
	}
		
	
	private void AStarSearch ( BoardPath bp, HashMap<Integer,VisitedEntry> visitedMap, PriorityQueue<BoardPath> queue, MoveRule moveRule, DistanceCache distanceCache )
	{
		
		if ( finished )
		{
			return;
		}
		
		if ( bp.board.isFinished() )
		{
			if ( Client.PRINT_COMMENTS )
			{
				System.out.println("alla boxar paa alla goals");
			}
			
			
			solution = createSolutionFromVisitedEntries( bp.lastVisitedEntry, bp.beginDirection );
			
			reportSolution( solution );
			return; 
		}
		
		for ( Move move : bp.board.getLegalMoves( bp.board.getPlayer() , moveRule) )
		{

			Board newBoard = bp.board.clone();
			Board potentialDualMove = newBoard.doMovePlayer( move.getDirectionToThis() );
		
			while(true)
			{
//				if ( Client.PRINT_COMMENTS_OLLE )
//				{
//					System.out.println( );
//					System.out.println("\tInnuti AStarSearch");
//					newBoard.printBoard();
//				}
				
//				Move.Direction reverse = move.getDirectionToThis().reverse();
//				
//				if (    bp.board.getCellType( move.doNewMove( reverse ).doNewMove(reverse) ).isBox() &&
//						newBoard.getCellType( move.doNewMove( reverse ) ).isBox() )
//				{
//					newBoard.printBoard();
//				}
						
				
				
				int newBoardHashCode = newBoard.hashCode();
				
//				System.out.println("nextState = \t"+newBoard.hashCode());
				
				VisitedEntry mapEntry = visitedMap.get( newBoard.hashCode() );
				
//				if ( !visitedMap.containsKey( newBoard.hashCode() ) )
				if ( mapEntry == null )
				{
					
//					newBoard.printBoard();

					VisitedEntry newEntry = new VisitedEntry( newBoardHashCode, move.getDirectionToThis(), bp.lastVisitedEntry, bp.beginDirection );
					
					visitedMap.put( newBoard.hashCode(), newEntry );

					iterationCounter++;
					
//					BoardPath newBP = new BoardPath( newBoard, null, 
//							bp.depth-1, bp.beginDirection, bp.boxManhattanDistanceMatrix, newEntry, distanceCache );
					BoardPath newBP = new BoardPath( newBoard, null, 
							bp.depth-1, bp.beginDirection, newEntry, distanceCache );
					
					
					queue.add( newBP );
				}
				else if ( mapEntry.beginDirection != bp.beginDirection && bp.beginDirection == BoardPath.BeginDirection.Forward )
				{
					
//					solution = createSolutionFromVisitedEntries( bp.lastVisitedEntry, bp.beginDirection );
//					
//					reportSolution( solution );
					
					VisitedEntry fromBegin = null;
					VisitedEntry fromEnd = null;
					
					String middle = null;
					
					if ( bp.beginDirection == BoardPath.BeginDirection.Forward )
					{
						fromBegin = bp.lastVisitedEntry;
						fromEnd = mapEntry;
						middle = move.getDirectionToThis().toString();
					}
					else
					{
						fromEnd = bp.lastVisitedEntry;
						fromBegin = mapEntry;
						middle = move.getDirectionToThis().reverse().toString();
					}
					


					String solBegin = createSolutionFromVisitedEntries( fromBegin , BoardPath.BeginDirection.Forward );
					String solEnd = createSolutionFromVisitedEntries( fromEnd, BoardPath.BeginDirection.Backwards );
					
//					solution = createSolutionFromVisitedEntries( fromBegin , BoardPath.BeginDirection.Forward ) +
//							createSolutionFromVisitedEntries( fromEnd, BoardPath.BeginDirection.Backwards );
					
//					System.out.println("SolBegin : "+solBegin);
//					System.out.println("solEnd   : "+solEnd);
//					System.out.println("middle   : "+middle);
					
					solution = solBegin+middle+solEnd;
					
//					System.out.println("L�SNING HITTAD AV FRAM+BAK!");
//					System.exit(1);
					
					reportSolution( solution );
					return; 
					
				}
				
				if ( potentialDualMove != null )
				{
					newBoard = potentialDualMove;
					potentialDualMove = null;
				}
				else
				{
					break;
				}
			}			
		}
	}
	
	private String createSolutionFromVisitedEntries( VisitedEntry lastEntry, BoardPath.BeginDirection beginDirection )
	{
		StringBuilder sb = new StringBuilder();

		while ( lastEntry != null )
		{
			if ( beginDirection == BoardPath.BeginDirection.Forward)
			{
				sb.append( lastEntry.direction.toString() );
			}
			else
			{
				sb.append( lastEntry.direction.reverse().toString() );
			}
			
//			System.out.println( entry.direction.toString() );
			
			lastEntry = lastEntry.lastEntryPointer;
		}
		
		if ( beginDirection == BoardPath.BeginDirection.Forward )
		{
			sb.reverse();
		}
		
		return sb.toString();
		
	}

}
